package cn.trigram.structure;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;
import java.util.function.Consumer;

/**
 * 二叉树树的工具类。 以下例的树为例子：
 * <pre>
 *       A
 *     ↙   ↘
 *    B     C
 *  ↙  ↘   ↙
 * D    E F
 * </pre>
 *
 * @author 一日看尽长安花
 * @date 2022/01/12 22:03:07
 */
public class BinaryTreeUtil {


  /**
   * 二叉树的前序非递归遍历。中->左->右
   * <p>
   * 遍历结果：A->B->D->E->C->F
   *
   * @param root
   *     根
   */
  public static void preOrderNonRecursive(BinaryTreeNode root, Consumer<BinaryTreeNode> consumer) {

    if (Objects.isNull(root)) {
      return;
    }
    Deque<BinaryTreeNode> stack = new ArrayDeque<>();
    stack.addFirst(root);
    while (!stack.isEmpty()) {
      /*按前序遍历，先处理局部树的根节点*/
      BinaryTreeNode node = stack.removeFirst();
      consumer.accept(node);
      /*按栈的先进后出规则，先压入右子节点，然后左子节点*/
      if (Objects.nonNull(node.getRight())) {
        stack.addFirst(node.getRight());
      }
      if (Objects.nonNull(node.getLeft())) {
        stack.addFirst(node.getLeft());
      }
    }
  }

  /**
   * 二叉树的中序非递归遍历。左->中->右
   * <p>
   * 遍历结果：D->B->E->A->F->C
   *
   * @param root
   *     根
   */
  public static void middleOrderNonRecursive(
      BinaryTreeNode root, Consumer<BinaryTreeNode> consumer
  ) {
    /*遍历的实时指针*/
    BinaryTreeNode        pointer = root;
    Deque<BinaryTreeNode> stack   = new ArrayDeque<>();
    while (!stack.isEmpty() || Objects.nonNull(pointer)) {
      if (Objects.nonNull(pointer)) {
        /*这部分判断满足先顺着树的分支查找左子节点*/
        stack.addFirst(pointer);
        pointer = pointer.getLeft();
      } else {
        /*当树的分支的左子节点找到底了，先处理栈顶的左子节点。*/
        pointer = stack.removeFirst();
        consumer.accept(pointer);
        /*处理完左子节点，将实时指针指向左子节点的右子节点继续找右子节点的左子节点*/
        pointer = pointer.getRight();
      }
    }
  }


  /**
   * 二叉树的后序非递归遍历。左->右->中
   * <p>
   * 正常遍历就算使用栈也难以维护进栈顺序。 所以利用双栈，其中一个作为后序遍历顺序的节点的镜像存储。
   * <p>
   * 然后倒腾出栈正好就是正常的后序顺序
   * <p>
   * 遍历结果：D->E->B->F->C->A
   *
   * @param root
   *     根
   */
  public static void postOrderNonRecursive(BinaryTreeNode root, Consumer<BinaryTreeNode> consumer) {

    if (Objects.isNull(root)) {
      return;
    }
    Deque<BinaryTreeNode> stack = new ArrayDeque<>();
    /*反转栈*/
    Deque<BinaryTreeNode> reversedStack = new ArrayDeque<>();
    reversedStack.addFirst(root);
    while (!reversedStack.isEmpty()) {
      BinaryTreeNode temp = reversedStack.removeFirst();
      stack.addFirst(temp);
      if (Objects.nonNull(temp.getLeft())) {
        reversedStack.addFirst(temp.getLeft());
      }
      if (Objects.nonNull(temp.getRight())) {
        reversedStack.addFirst(temp.getRight());
      }
    }
    while (!stack.isEmpty()) {
      BinaryTreeNode node = stack.removeFirst();
      consumer.accept(node);
    }
  }

  /**
   * 层序遍历非递归
   * <p>
   * 遍历结果: A->B->C->D->E->F
   */
  public static void sequenceNonRecursive(BinaryTreeNode root, Consumer<BinaryTreeNode> consumer) {

    if (Objects.isNull(root)) {
      return;
    }
    /*迭代队列*/
    Deque<BinaryTreeNode> iteratorDeque = new ArrayDeque<>();
    /*消费队列*/
    Deque<BinaryTreeNode> consumerDeque = new ArrayDeque<>();
    consumerDeque.addFirst(root);
    while (!consumerDeque.isEmpty()) {
      while (!consumerDeque.isEmpty()) {
        BinaryTreeNode node = consumerDeque.removeFirst();
        consumer.accept(node);
        iteratorDeque.addLast(node);
      }
      while (!iteratorDeque.isEmpty()) {
        BinaryTreeNode node = iteratorDeque.removeFirst();
        if (Objects.nonNull(node.getLeft())) {
          consumerDeque.addLast(node.getLeft());
        }
        if (Objects.nonNull(node.getRight())) {
          consumerDeque.addLast(node.getRight());
        }
      }
    }

  }

}
